/*
 * @Author: your name
 * @Date: 2021-06-28 19:06:45
 * @LastEditTime: 2021-06-28 20:35:58
 * @LastEditors: Please set LastEditors
 * @Description: In User Settings Edit
 * @FilePath: \LinkList\815\815.cpp
 */
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
#include <iostream>
#include <unordered_set>
#include <chrono>
#include <unordered_set>
#define DEBUG ;
using namespace std;
using namespace chrono;
class Solution {
public:
    int numBusesToDestination(vector<vector<int>>& routes, int source, int target) {

        if(target==source)
        return 0; 
        unordered_set<int>  visited ;
        queue<int> q ;
        q.push(source);
        int step =0;
        while(q.size()!=0)
        {
            int sz = q.size();
        
            for (int i =0;i<sz;++i)
            {
                auto node = q.front();
                q.pop();
                if(node==target)
                return step;
                // visited.insert(node);
                for(auto  ptr=routes.begin();ptr!=routes.end();++ptr)
                {
                    auto route =*ptr;
                    auto ite= find(route.begin(),route.end(),node);
                    if(ite!=route.end())
                    {
                        for(auto subptr=route.begin();subptr!=route.end();++subptr)
                        {

                            auto station=*subptr;
                            if(station==target)
                                return step+1;
                            else 
                            {

                                if(!visited.count(station))
                                        {q.push(station);
                                        visited.insert(station);}
                                if(station==node)
                                {
                                    if((subptr+1)==route.end())
{
                                        route.erase(subptr);
                                        
                                        break;}
                                        else  route.erase(subptr);
                            subptr--;
                            }
                            }
                        }
                    }
                    // else 
                    //     continue ;
                    // routes.erase(ptr);
                }
            }
            step++;
        }
        return -1 ;
    }
};

int main()
{
    vector<vector<int > > routes ={{6,12},{2,9,18},{1,3,5,9,16},{4},{2,13,19}};
int source =3;
 int target =5;
//    vector<vector<int > > routes ={{25,33},{3,5,13,22,23,29,37,45,49},{15,16,41,47},{5,11,17,23,33},{10,11,12,29,30,39,45},{2,5,23,24,33},{1,2,9,19,20,21,23,32,34,44},{7,18,23,24},{1,2,7,27,36,44},{7,14,33}};
//      int source =7;
//      int target =47;
    Solution s1;
   cout <<  s1.numBusesToDestination(routes,source,target);
}